def get_j(serviceitems,dataitems,graph,i):
    list=[]
    for j in range(len(dataitems)):
        if graph[i][j][0]==1:
            list.append(j)
    return list


#garph level output
# https://code.activestate.com/recipes/577876-printing-breadth-first-levels-of-a-graph-or-tree/
# def printBfsLevels(graph,start,serviceitems="",dataitems=""):
#   queue=[start]
#   path=[]
# #   levelaccess=[]
#   currLevel=1
#   levelMembers=1
#   height=[(0,start)]
#   levelaccess=[start]
#   childCount=0
#   print(queue)

#   while queue:
#     visNode=queue.pop(0)
#     if visNode not in path:
#       if  levelMembers==0:
#         levelMembers=childCount
#         childCount=0
#         currLevel=currLevel+1
#       queue=queue+get_j(serviceitems,dataitems,graph,visNode)#graph.get(visNode,[])
#       if levelMembers > 0:
#         levelMembers=levelMembers-1
#         for node in get_j(serviceitems,dataitems,graph,visNode):#graph.get(visNode,[]):
#             if node not in levelaccess:
#                 childCount=childCount+1
#                 levelaccess.append(node)
#                 height.append((currLevel,node))
#         #   x=0
#       path=path+[visNode]

#   prevLevel=None
  
#   for v,k in sorted(height):
#         if prevLevel!=v:
#           if prevLevel!=None:
#             print ("")
#         prevLevel=v
#         print (str(k)+",",end="")
#   print("")
#   return height

# g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13],6:[1],15:[16]}
# printBfsLevels(g,15)




#Find all of the cycles in the graph
# https://ittone.ma/ittone/python-find-all-the-cycle-in-a-graph-in-a-dictionary/
def get_all_paths(graph, start, end,serviceitems,dataitems):
  path  = []
  paths = []
  queue = [(start, end, path)]
  while queue:
    start, end, path = queue.pop()
    path = path + [start]
    # print(path)
    if start == end:
      paths.append(path)
      
    # for node in set(graph[start]).difference(path):
    for node in set(get_j(serviceitems,dataitems,graph,start)).difference(path):
      queue.append((node, end, path))

  return paths


# def find_cycle(graph, s,serviceitems,dataitems):
#   possible_cycle = []
# #   for nodes in set(graph[s]):
#   for nodes in set(get_j(serviceitems,dataitems,graph,s)):
#     possible_cycle += get_all_paths(graph, nodes, s,serviceitems,dataitems)

#   if len(possible_cycle) == 0:
#     return []
#   else:
#     maxlength = max(possible_cycle, key = len)
#     return maxlength


# graph = {0: [5, 8, 10], 1: [2, 6], 2: [1, 3], 3: [1, 5], 4: [2, 5], 5: [4, 6, 9], 6: [1, 3, 9], 7: [6], 8: [7, 10], 9: [0, 6, 8, 10], 10: []}

# print(find_cycle(graph, 2))


import json
import numpy as np

def read_model():
    with open('/mnt/d/WSL/consisi-demo/model.json','r',encoding='utf8') as fp:
        json_data = json.load(fp)
        return json_data

def arc_graph(dataobj):
    # (is_edge,color)
    data=dataobj["Data"].copy()
    servers=dataobj["Server"]
    arc=dataobj["Dep"]
    degra=dataobj["Degrade"]
    

    data.extend(servers)
    # edge_items.append(data)
    # edge_items.append(servers)
    edge_len=len(data)

    graph=np.arange(edge_len*edge_len).reshape((edge_len, edge_len))

    graph_list=[]
    for i in range(edge_len):
        tmp_list=[]
        for j in range(edge_len):
            tmp_list.append([-1,-1])
        graph_list.append(tmp_list)
            

    graph=np.array(graph_list)
    
    for item in arc:
        op=""

        if("<-->" in item):
            x=item.split("<-->")
            op="<-->"
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            graph[index0][index1]=[1,0]
            graph[index1][index0]=[1,0]

        elif("-->" in item):    
            x=item.split("-->")
            op="-->" 
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            graph[index0][index1]=[1,0]
            # graph[index1,index0]=(1,-1)

        elif("<--" in item):
            x=item.split("<--")
            op="<--"
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            # graph[index0,index1]=(1,-1)
            graph[index1][index0]=[1,0]
        else:
            print("unknown operator!!")

    graph_org=graph.copy()
    
    
    #依赖传递
    to_d=[]
    d_to=[]
    for x in dataobj["Data"]:
      to_d.append([])
      d_to.append([])

    for d_item in dataobj["Data"]:
      i=data.index(d_item)
      for all_item in dataobj["Server"]:
        j=data.index(all_item)
        if graph[i][j][0]==1:
          d_to[i].append(j)
          graph[i][j]=[-1,-1]
        if graph[j][i][0]==1:
          to_d[i].append(j)
          graph[j][i]=[-1,-1]
    
    for index in range(len(d_to)):
      for item_d_to in d_to[index]:
        for item_to_d in to_d[index]:
          if item_d_to !=item_to_d:
            graph[item_to_d][item_d_to]=[1,0]

    graph_dep=graph.copy()

    #降级
    for item in degra:
        op=""

        if("<-->" in item):
            x=item.split("<-->")
            op="<-->"
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            graph[index0][index1]=[1,1]
            graph[index1][index0]=[1,1]

        elif("-->" in item):    
            x=item.split("-->")
            op="-->" 
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            graph[index0][index1]=[1,1]
            # graph[index1,index0]=(1,-1)

        elif("<--" in item):
            x=item.split("<--")
            op="<--"
            index0=data.index(x[0]) 
            index1=data.index(x[1])
            # graph[index0,index1]=(1,-1)
            graph[index1][index0]=[1,1]
        else:
            print("unknown operator!!")



    return data,graph_dep,graph_org,graph
        
def min_in_degree(serviceitems,dataitems,graph):
  indegree=[]

  for i in range(len(dataitems)):
    indegree.append(0)
    for j in range(len(dataitems)):
      if graph[j][i][0]==1:
        indegree[i]+=1
  
  n=9999999
  index=-1
  for i in range(len(indegree)):
    if indegree[i]<n:
      index=i

  index_list=[]
  for i in range(len(indegree)):
    if indegree[index]==indegree[i]:
      index_list.append(i)
  return index_list

#找最小初始点，需完善
# def get_start_node(serviceitems,dataitems,graph):
#     start_node=[]


#     for j in range(len(dataitems)):
#         for item in serviceitems:
#             i=dataitems.index(item)
#             if graph[i][j][0]==1:
#                 flag=True
#                 for k in range(len(dataitems)):
#                     if dataitems[k] in serviceitems and graph[k][i][0]==1:
#                         flag=False
#                 if flag==True and i not in start_node:        
#                     start_node.append(i)
    
#     if len(start_node)==0:
#         n=min_in_degree(serviceitems,dataitems,graph)
#         c=find_cycle(graph,n[0],serviceitems,dataitems)
#         if n[0] in c:
#           # return 
#           start_node.append(c)
    
#     return start_node

import networkx as nx

def find_cycle(graphx,serviceitems,dataitems,flag,file):#flag=true dataitems
        g=nx.DiGraph()
        for item in serviceitems:
            g.add_node(item)

        # G.add_node(
        # g = pydotplus.Dot()
        # g.set_charset('latin1')
        # g.add_node(pydotplus.Node(node1))
        # if flag:
        #   for item in dataitems:
        #     g.add_node(pydotplus.Node(item))
        # else:
        #   for item in serviceitems:
        #     g.add_node(pydotplus.Node(item))

        for i in range(len(dataitems)):
          for j in range(len(dataitems)):
            if graphx[i][j][0]==1:
              c="black"
              if graphx[i][j][1]==1:
                c="green"
              g.add_edge(dataitems[i],dataitems[j],color=c)
              # g.add_edge(pydot.Edge(1,dataitems[j])) 
          # g.add_edge(pydotplus.Edge(node1, node2))

        needed=[]
        cycles=list(nx.simple_cycles(g))
        for cycle in cycles:
            flaggreen=False
            flagblack=False
            for sn_index in range(len(cycle)):
              cur_edge=g.edges._adjdict[cycle[sn_index]][cycle[(sn_index+1)%len(cycle)]]
              if cur_edge["color"]=="green":
                flaggreen=True
              elif cur_edge["color"]=="black":
                flagblack=True
            
            if flaggreen and flagblack:
                needed.append(cycle)
        return needed

        # g2 = pydotplus.graph_from_dot_data(g.to_string())


import pydotplus
def drawgraph(graphx,serviceitems,dataitems,flag,file):#flag=true dataitems

        g = pydotplus.Dot()
        # g.set_charset('latin1')
        # g.add_node(pydotplus.Node(node1))
        # if flag:
        #   for item in dataitems:
        #     g.add_node(pydotplus.Node(item))
        # else:
        #   for item in serviceitems:
        #     g.add_node(pydotplus.Node(item))

        for i in range(len(dataitems)):
          for j in range(len(dataitems)):
            if graphx[i][j][0]==1:
              c="black"
              if graphx[i][j][1]==1:
                c="green"
              g.add_edge(pydotplus.Edge(dataitems[i],dataitems[j],color=c))
              # g.add_edge(pydot.Edge(1,dataitems[j])) 
          # g.add_edge(pydotplus.Edge(node1, node2))

        g.write(file, format='png') 
        # g2 = pydotplus.graph_from_dot_data(g.to_string())